package advance.day04;


import java.util.HashMap;

/**
 * 描述：
 *      累加和为sum的最长子数组，返回该数组的长度。时间复杂度O(n)
 *      思路：如果累加和为k的最长子数组的范围是i~j，那么k = 子数组和[0~j] - 子数组和[0,i-1]
 * @author hl
 * @version 1.0
 * @date 2020/11/9 16:04
 */
public class LongestSunSubArrayLength {
    public static int maxLength(int[] nums, int k){
        //保存索引位置上的累加和
        HashMap<Integer, Integer> indexSumMap = new HashMap<>();
        //确保从0开始的位置可以被统计到
        indexSumMap.put(0, -1);
        int len = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (indexSumMap.containsKey(sum - k)) {
                len = Math.max(i - indexSumMap.get(sum - k),len);
            }
            if (!indexSumMap.containsKey(sum)) {
                indexSumMap.put(sum, i);
            }
        }
        return len;
    }
}
